package xquery;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.*;

import org.w3c.dom.Node;
import org.w3c.dom.bootstrap.DOMImplementationRegistry;
import org.w3c.dom.ls.DOMImplementationLS;
import org.w3c.dom.ls.LSOutput;
import org.w3c.dom.ls.LSSerializer;

import xquery.XPathComposedExp.XPathOperator;
import xquery.XPathSimpleExp.XPathNodeType;
import xquery.XQuerySimpleCond.XQueryOperator;
import xquery.XQuerySimpleExp.Type;
import xqueryparser.SimpleNode;
import xqueryparser.XQueryParser;
import xqueryparser.XQueryParserTreeConstants;

public class XQueryProcessor implements XQueryParserTreeConstants{

	public static void main(String[] args) throws Exception {
		//long start = System.currentTimeMillis();
		XQueryProcessor proc = new XQueryProcessor();
		
		FileInputStream xqueryfile = new FileInputStream("xquery8.txt");
		XQueryParser parser = new XQueryParser(xqueryfile);
		
		SimpleNode jjt = parser.XQuery();
		
		XQExpression xquery = proc.jjt2ast(jjt);
		
		long start = System.currentTimeMillis();
//		proc.naiveEval(xquery);
		proc.optimizedEval(xquery);

//		System.out.println(data);
		
		
		xqueryfile.close();
		
		System.out.println(System.currentTimeMillis() - start);
	}
	private void naiveEval(XQExpression xquery)
	{
		XPathData data = xquery.eval(new XQContext(), new ArrayList<Node>());
		PrintWriter writer;
		try {
			writer = new PrintWriter(new BufferedWriter(new FileWriter("result")));
			writer.print(data.toString());
		    writer.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	   	
	}
	private void optimizedEval(XQExpression xquery)
	{
		XQueryProcessor proc = new XQueryProcessor();
		XQExpression optimizedXQuery = proc.optimize(xquery);
		System.out.println(optimizedXQuery);		
		XPathData data = optimizedXQuery.eval(new XQContext(), new ArrayList<Node>());
		PrintWriter writer;
		try {
			writer = new PrintWriter(new BufferedWriter(new FileWriter("result1")));
			writer.print(data.toString());
		    writer.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
	private XQExpression optimize(XQExpression xquery)
	{
		XQueryForExp forExp = (XQueryForExp)xquery;
		XQVarExpPair[] forclauses = forExp.forclause;
		ArrayList<HashSet<String>> group = new ArrayList<HashSet<String>>();
		ArrayList<ArrayList<XQuerySimpleCond>> predicates = new ArrayList<ArrayList<XQuerySimpleCond>>();
		for(XQVarExpPair varExpPair: forclauses)
		{
			if(varExpPair.exp instanceof XPathComposedExp)
			{
				HashSet<String> set = new HashSet<String>();
				ArrayList<XQuerySimpleCond> predicate = new ArrayList<XQuerySimpleCond>();
				set.add(varExpPair.var);
				group.add(set);
				predicates.add(predicate);
			}
			if (varExpPair.exp instanceof XQueryPathExp)
			{
				String var = ((XQuerySimpleExp)((XQueryPathExp)varExpPair.exp).xquery).value;
				for(HashSet<String> set : group)
				{
					if(set.contains(var))
					{
						set.add(varExpPair.var);
					}
				}
			}
		}
		XQuerySimpleCond whereclause = (XQuerySimpleCond)forExp.whereclause;
		XQExpression[] conds;
		XQueryJoinExp joinExp = new XQueryJoinExp();
		ArrayList<String> varList1 = new ArrayList<String>();
		ArrayList<String> varList2 = new ArrayList<String>();
		ArrayList<ArrayList<String>> varLists = new ArrayList<ArrayList<String>>();
		varLists.add(varList1);
		varLists.add(varList2);
		if(whereclause.op == XQueryOperator.AND)
		{
			conds = whereclause.operand;
		}
		else
		{
			conds = new XQExpression[1];
			conds[0] = whereclause;
		}
		for(int i=0;i<conds.length;i++)
		{
			XQuerySimpleCond exp = (XQuerySimpleCond)conds[i];
			XQuerySimpleExp[] operand = new XQuerySimpleExp[2];
			operand[0] = (XQuerySimpleExp)exp.operand[0];
			operand[1] = (XQuerySimpleExp)exp.operand[1];
			if(operand[0].type == Type.STRING || operand[1].type == Type.STRING)
			{
				for(int j = 0;j<group.size();j++)
				{
					HashSet<String> set = group.get(j);
					if(operand[0].type == Type.VAR)
					{
						if (set.contains(operand[0].value))
						{
							predicates.get(j).add(exp);
							break;
						}
					}
					if(operand[1].type == Type.VAR)
					{
						if (set.contains(operand[1].value))
						{
							predicates.get(j).add(exp);
							break;
						}
					}
				}
			}
			else
			{					
				HashSet<String> set1 = group.get(0);
				HashSet<String> set2 = group.get(1);
				if (set1.contains(operand[0].value))
				{
					if(set2.contains(operand[1].value))
					{
						varList1.add(operand[0].value);
						varList2.add(operand[1].value);
					}
					else
					{
						predicates.get(0).add(exp);
					}
				}
				else if (set1.contains(operand[1].value))
				{
					if(set2.contains(operand[0].value))
					{
						varList1.add(operand[1].value);
						varList2.add(operand[0].value);
					}
					else
					{
						predicates.get(1).add(exp);
					}				
				}
			}
		}
		if (varList1.isEmpty())
			return xquery;
		XQExpression returnclause = forExp.returnclause;
		HashSet<String> variables = new HashSet<String>();
		rewriteReturn(forExp,returnclause,variables,forclauses);
		joinExp.forExp = new XQueryForExp[group.size()];
		for(int i=0;i<group.size();i++)
		{
			XQueryForExp newForExp = new XQueryForExp();
			newForExp.forclause = new XQVarExpPair[group.get(i).size()];
			int k = 0;
			for(int j=0;j<forclauses.length;j++)
			{
				if(group.get(i).contains(forclauses[j].var))
				{
					newForExp.forclause[k] = forclauses[j];
					k++;
				}
			}
			ArrayList<XQuerySimpleCond> predicate = predicates.get(i);
			if(predicate.size() == 1)
			{
				newForExp.whereclause = predicate.get(0);
			}
			else if(predicate.size() > 1)
			{
				XQuerySimpleCond newwhereclause= new XQuerySimpleCond();
				newwhereclause.op = XQueryOperator.AND;
				newwhereclause.operand = predicate.toArray(new XQuerySimpleCond[0]);
				newForExp.whereclause = newwhereclause;
			}
			variables.addAll(varLists.get(i));
			group.get(i).retainAll(variables);
			int size = group.get(i).size();
			XQueryTagExp newreturnclause =  new XQueryTagExp();
			newreturnclause.tagName = "tuple";
			if(size > 1)
			{
				XQueryComposedExp list = new XQueryComposedExp();
				list.xquery = new XQueryTagExp[size];
				int j = 0;
				XQueryTagExp tagExp = null;
				XQuerySimpleExp tagQuery = null;
				Iterator<String> it = group.get(i).iterator();
				while(it.hasNext())
				{
					tagExp = new XQueryTagExp();
					tagExp.tagName = it.next();
					tagQuery = new XQuerySimpleExp();
					tagQuery.type = Type.VAR;
					tagQuery.value = tagExp.tagName;
					tagExp.xquery = tagQuery;
					list.xquery[j] = tagExp;
					j++;
				}
				newreturnclause.xquery = list;
			}
			else
			{
				Iterator<String> it = group.get(i).iterator();
				XQueryTagExp tagExp = new XQueryTagExp();
				tagExp.tagName = it.next();
				XQuerySimpleExp tagQuery = new XQuerySimpleExp();
				tagQuery.type = Type.VAR;
				tagQuery.value = tagExp.tagName;
				tagExp.xquery = tagQuery;
				newreturnclause.xquery = tagExp;
			}
			newForExp.returnclause = newreturnclause;
			joinExp.forExp[i] = newForExp;
		}
		joinExp.varLists = varLists;
		XQueryForExp newForExp = new XQueryForExp();
		XQVarExpPair[] forclause = new XQVarExpPair[1];
		forclause[0] = new XQVarExpPair("tuple",joinExp);
		newForExp.forclause = forclause;
		newForExp.returnclause = forExp.returnclause;
		return newForExp;
	}
	private void rewriteReturn(XQExpression parent, XQExpression current, HashSet<String> variables,XQVarExpPair[] forclauses)
	{
		if(current instanceof XQueryTagExp)
		{
			XQueryTagExp exp = (XQueryTagExp)current;
			rewriteReturn(current, exp.xquery, variables,forclauses);
		}
		else if(current instanceof XQueryComposedExp)
		{
			XQueryComposedExp exp = (XQueryComposedExp)current;
			for(int i=0;i<exp.xquery.length;i++)
			{
				rewriteReturn(current, exp.xquery[i], variables,forclauses);
			}
		}
		else if(current instanceof XQueryPathExp)
		{
			XQueryPathExp pathexp = (XQueryPathExp)current;
			XQuerySimpleExp exp = (XQuerySimpleExp)pathexp.xquery;
			variables.add(exp.value);
			XPathSimpleExp path3 = findTag(exp.value,forclauses);
			XQuerySimpleExp exp1 = new XQuerySimpleExp();
			XPathComposedExp path1 = new XPathComposedExp();
			exp1.type = Type.VAR;
			exp1.value = "tuple";
			if (pathexp.xpath instanceof XPathSimpleExp)
			{
				XPathSimpleExp path = (XPathSimpleExp)pathexp.xpath;
				path1.op = new XPathOperator[2];
				path1.op[0] = XPathOperator.DIRECT;
				path1.op[1] = pathexp.relation;
				path1.operand = new XPathExp[3];
				XPathSimpleExp path2 = new XPathSimpleExp();
				path2.type = XPathNodeType.TAG;
				path2.value = exp.value;
				path1.operand[0] = path2;
				path1.operand[1] = path3;
				path1.operand[2] = path;				
				pathexp.xpath = path1;
				pathexp.xquery = exp1;				
			}
			else
			{
				XPathComposedExp path = (XPathComposedExp)pathexp.xpath;
				path1.op = new XPathOperator[path.op.length+2];
				path1.op[0] = XPathOperator.DIRECT;
				path1.op[1] = pathexp.relation;
				for(int i=2;i<path1.op.length;i++)
				{
					path1.op[i] = path.op[i-2];
				}
				path1.operand = new XPathExp[path.operand.length+2];
				XPathSimpleExp path2 = new XPathSimpleExp();
				path2.type = XPathNodeType.TAG;
				path2.value = exp.value;
				path1.operand[0] = path2;
				path1.operand[1] = path3;
				for(int i=2;i<path1.operand.length;i++)
				{
					path1.operand[i] = path.operand[i-2];
				}
				pathexp.xpath = path1;
				pathexp.xquery = exp1;
			}
		}
		else if(current instanceof XQuerySimpleExp)
		{
			XQuerySimpleExp exp = (XQuerySimpleExp)current;			
			if (exp.type == XQuerySimpleExp.Type.VAR)
			{	
				XQueryPathExp exp1 = new XQueryPathExp();
				XQuerySimpleExp exp2 = new XQuerySimpleExp();
				XPathComposedExp path2 = new XPathComposedExp();
				XPathSimpleExp path3 = findTag(exp.value,forclauses);
				path2.op = new XPathOperator[1];
				path2.op[0] = XPathOperator.DIRECT;
				XPathSimpleExp path1 = new XPathSimpleExp();
				variables.add(exp.value);
				path1.type = XPathNodeType.TAG;
				path1.value = exp.value;
				path2.operand = new XPathSimpleExp[2];
				path2.operand[0] = path1;
				path2.operand[1] = path3;
				exp2.type = Type.VAR;
				exp2.value = "tuple";
				exp1.relation = XPathOperator.DIRECT;
				exp1.xquery = exp2;
				exp1.xpath = path2;
				if(parent instanceof XQueryForExp)
				{
					((XQueryForExp)parent).returnclause = exp1;
				}
				else if(parent instanceof XQueryTagExp)
				{
					((XQueryTagExp)parent).xquery = exp1;
				}
				else if(parent instanceof XQueryComposedExp)
				{
					XQueryComposedExp list = (XQueryComposedExp)parent;
					for(int i=0; i<list.xquery.length;i++)
					{
						if(list.xquery[i] == exp)
						{
							list.xquery[i] = exp1;
							break;
						}
					}
				}
			}				
		}
	}
	private XPathSimpleExp findTag(String value,XQVarExpPair[] forclauses)
	{
		XPathSimpleExp path3 = new XPathSimpleExp();
		XQExpression xquery = null;
		for(int i=0;i<forclauses.length;i++)
		{
			if(value.equals(forclauses[i].var))
			{
				xquery = forclauses[i].exp;
				break;
			}
		}
		if(xquery instanceof XPathComposedExp)
		{
			XPathComposedExp xquery1 = (XPathComposedExp)xquery;
			if(xquery1.operand[xquery1.operand.length-1] instanceof XPathSimpleExp)
			{
				path3 = (XPathSimpleExp)(xquery1.operand[xquery1.operand.length-1]);
			}
			else
			{
				XPathComposedExp operands = (XPathComposedExp)xquery1.operand[xquery1.operand.length-1];
				path3 = (XPathSimpleExp)operands.operand[operands.operand.length-1];
			}			
		}
		else if(xquery instanceof XQueryPathExp)
		{
			XQueryPathExp xquery1 = (XQueryPathExp)xquery;
			XQExpression xpath = xquery1.xpath;
			if(xpath instanceof XPathSimpleExp)
			{
				path3 = (XPathSimpleExp)xpath;
			}
			else if(xpath instanceof XPathComposedExp)
			{
				XPathComposedExp xpath1 = (XPathComposedExp)xpath;
				path3 = (XPathSimpleExp)xpath1.operand[xpath1.operand.length-1];
			}
		}
		return path3;
	}
	private XQExpression jjt2ast(SimpleNode jjt) {
		
		XPathSimpleExp simpleXPath = new XPathSimpleExp();
		
		switch(jjt.getId()) {
		case JJTAPATH:
		case JJTUNIONPATH:
		case JJTRPATH:
		case JJTFILTEREXP:
		case JJTORFILTER:
		case JJTANDFILTER:
		case JJTCOMPAREFILTER:
			return createComposedXPath(jjt);
		case JJTDOC:
			simpleXPath.type = XPathNodeType.DOC;
			simpleXPath.value = (String)jjt.getAttr("filename");
			return simpleXPath;
		case JJTSYMBOL:
			simpleXPath.type = XPathNodeType.string2type((String)jjt.getAttr("value"));
			return simpleXPath;
		case JJTID:
			simpleXPath.type = XPathNodeType.TAG;
			simpleXPath.value = (String)jjt.getAttr("value");
			return simpleXPath;
		case JJTTEXT:
			simpleXPath.type = XPathNodeType.TEXT;
			return simpleXPath;
		case JJTXQUERY:
			return jjt2ast((SimpleNode)jjt.jjtGetChild(0));
		case JJTCOMBINEDXQ:
			XQueryComposedExp xqueryComposedExp = new XQueryComposedExp();
			int numChildren = jjt.jjtGetNumChildren();
			xqueryComposedExp.xquery = new XQExpression[numChildren];
			for(int i=0;i<numChildren;i++) {
				xqueryComposedExp.xquery[i] = jjt2ast((SimpleNode)jjt.jjtGetChild(i));
			}
			return xqueryComposedExp;
		case JJTPATHXQ:
			XQueryPathExp xqueryPath = new XQueryPathExp();
			xqueryPath.xquery = jjt2ast((SimpleNode)jjt.jjtGetChild(0));
			xqueryPath.xpath = jjt2ast((SimpleNode)jjt.jjtGetChild(1));
			xqueryPath.relation = XPathOperator.string2op((String)jjt.getAttr("relation"));
			return xqueryPath;
		case JJTTAGEXP:
			XQueryTagExp xqueryTag = new XQueryTagExp();
			xqueryTag.tagName = (String)jjt.getAttr("tagname");
			xqueryTag.xquery = jjt2ast((SimpleNode)jjt.jjtGetChild(0));
			return xqueryTag;
		case JJTVAR:{
			XQuerySimpleExp xquerySimple = new XQuerySimpleExp();
			xquerySimple.value = (String)jjt.getAttr("var");
			xquerySimple.type = Type.VAR;
			return xquerySimple;
			}
		case JJTSTRING:{
			XQuerySimpleExp xquerySimple = new XQuerySimpleExp();
			xquerySimple.value = (String)jjt.getAttr("string");
			xquerySimple.type = Type.STRING;
			return xquerySimple;
			}
		case JJTORCOND:
		case JJTANDCOND:
		case JJTEMPTYCOND:
		case JJTCOMPARECOND:
		case JJTNOTCOND:
			return createCond(jjt);
		case JJTFORXQ:
			return createForExp(jjt);
		case JJTSOMECOND:
			return createSomeCond(jjt);
		case JJTLETXQ:
			return createLetExp(jjt);
		}
		return null;
	}
	
	private XPathComposedExp createComposedXPath(SimpleNode jjt) {
		XPathComposedExp path = new XPathComposedExp();
		int numChildren = jjt.jjtGetNumChildren();
		path.operand = new XPathExp[numChildren];
		for(int i=0;i<numChildren;i++) {
			path.operand[i] = (XPathExp)jjt2ast((SimpleNode)jjt.jjtGetChild(i));
		}
		path.op = new XPathComposedExp.XPathOperator[numChildren-1];
		
		switch(jjt.getId()) {
		case JJTAPATH:
		case JJTCOMPAREFILTER:
			path.op[0] = XPathOperator.string2op((String)jjt.getAttr("relation"));
			break;
		case JJTUNIONPATH:
			Arrays.fill(path.op, XPathOperator.UNION);
			break;
		case JJTFILTEREXP:
			Arrays.fill(path.op, XPathOperator.FILTER);
			break;
		case JJTORFILTER:
			Arrays.fill(path.op, XPathOperator.OR);
			break;
		case JJTANDFILTER:
			Arrays.fill(path.op, XPathOperator.AND);
			break;
		case JJTRPATH:
			ArrayList<String> relations = (ArrayList<String>) jjt.getAttr("relation");
			for(int i=0;i<path.op.length;i++)
				path.op[i] = XPathOperator.string2op(relations.get(i));
			break;
		default:
			assert(false);
		}
		
		return path;
	}
	
	private XQuerySimpleCond createCond(SimpleNode jjt) {
		XQuerySimpleCond cond = new XQuerySimpleCond();
		
		switch(jjt.getId()) {
		case JJTORCOND:
			cond.op = XQueryOperator.OR; break;
		case JJTANDCOND:
			cond.op = XQueryOperator.AND; break;
		case JJTEMPTYCOND:
			cond.op = XQueryOperator.EMPTY; break;
		case JJTCOMPARECOND:
			if(jjt.getAttr("relation") == null)
			{
				return createCond((SimpleNode)jjt.jjtGetChild(0));
			}
			else
			{
			cond.op = XQueryOperator.string2op((String)jjt.getAttr("relation"));
			}
			break;
		case JJTNOTCOND:
			cond.op = XQueryOperator.NOT; break;
		}
		
		int numChildren = jjt.jjtGetNumChildren();
		cond.operand = new XQExpression[numChildren];
		
		for(int i=0;i<cond.operand.length;i++)
			cond.operand[i] = jjt2ast((SimpleNode)jjt.jjtGetChild(i));
		
		return cond;
	}
	
	private XQueryForExp createForExp(SimpleNode jjt) {
		XQueryForExp result = new XQueryForExp();
		
		int numChildren = jjt.jjtGetNumChildren();
		result.forclause = getVarExpPairs((SimpleNode)jjt.jjtGetChild(0));
		result.returnclause = jjt2ast((SimpleNode)jjt.jjtGetChild(numChildren-1).jjtGetChild(0));
		
		for(int i=1;i<numChildren;i++) {
			SimpleNode child = (SimpleNode)jjt.jjtGetChild(i);
			switch(child.getId()) {
			case JJTLETCLAUSE:
				result.letclause = getVarExpPairs((SimpleNode)jjt.jjtGetChild(i)); break;
			case JJTWHERECLAUSE:
				result.whereclause = jjt2ast((SimpleNode)jjt.jjtGetChild(i).jjtGetChild(0));
			}
		}
		
		return result;
	}
	private XQueryLetExp createLetExp(SimpleNode jjt) {
		XQueryLetExp result = new XQueryLetExp();
		result.letclause = getVarExpPairs((SimpleNode)jjt.jjtGetChild(0));
		result.xq = jjt2ast((SimpleNode)jjt.jjtGetChild(1));
	
		return result;
	}	
	private XQVarExpPair[] getVarExpPairs(SimpleNode jjt) {
		int numChildren = jjt.jjtGetNumChildren();
		
		XQVarExpPair[] result = new XQVarExpPair[numChildren/2];
		
		for(int i=0;i<numChildren;i+=2) {
			String var = (String)((SimpleNode)jjt.jjtGetChild(i)).getAttr("var");
			XQExpression exp = jjt2ast(((SimpleNode)jjt.jjtGetChild(i+1)));
			result[i/2] = new XQVarExpPair(var, exp);
		}
		
		return result;
	}
	
	private XQuerySomeCond createSomeCond(SimpleNode jjt) {
		XQuerySomeCond result = new XQuerySomeCond();
		
		int numChildren = jjt.jjtGetNumChildren();
		result.someclause = getVarExpPairs((SimpleNode)jjt.jjtGetChild(0));
		result.satisfiesclause = jjt2ast((SimpleNode)jjt.jjtGetChild(numChildren-1));
		
		return result;
	}
}
